package com.linc.ds;

import java.util.Arrays;

public class MyArrayList<E extends Comparable<E>> {

  private Object[] data;
  private Integer size = 8;
  private Integer curr = 0;

  public MyArrayList() {
    data = new Object[size];
  }

  Boolean add(E element) {
    if (curr == size - 1) {
      // 需要扩充
      size <<= 1;
      try {
        data = Arrays.copyOf(data, size);
      } catch (Exception e) {
        return false;
      }
    }
    data[curr] = element;
    curr++;
    return true;
  }

  /**
   * @param e - 插入元素
   * @param index - 该元素放置的位置
   * @return - 成功/失败
   */
  Boolean add(E e, int index) {
    if (index < 0 || index > curr) {
      return false;
    }

    if (curr == size - 1) {
      size <<= 1;
      data = Arrays.copyOf(data, size);
    }

    System.arraycopy(data, index, data, index + 1, curr - index);
    data[index] = e;
    curr++;
    return true;
  }

  @SuppressWarnings("unchecked")
  E get(int index) {
    return index >= curr ? null : (E) data[index];
  }

  @SuppressWarnings("unchecked")
  E del(int index) {
    if (index >= curr || index < 0) return null;
    E r = (E) data[index];
    System.arraycopy(data, index + 1, data, index, curr - 1 - index);
    curr--;
    return r;
  }

  @Override
  public String toString() {
    StringBuilder builder = new StringBuilder();
    builder.append(this.getClass().getSimpleName()).append(":[");
    for (int i = 0; i < curr - 1; i++) {
      builder.append(data[i]).append(", ");
    }
    if (curr > 0) {
      builder.append(data[curr - 1]);
    }
    builder.append("]");
    return builder.toString();
  }

  private void swap(int i, int j) {
    Object t = data[i];
    data[i] = data[j];
    data[j] = t;
  }

  /** 排序 - 范围从0到curr-1 */
  @SuppressWarnings("unchecked")
  public void bubbleSort() {
    for (int i = 0; i < curr - 1; i++) {
      for (int j = 0; j < curr - 1 - i; j++) {
        if (((E) data[j]).compareTo((E) data[j + 1]) > 0) {
          swap(j, j + 1);
        }
      }
    }
  }

  @SuppressWarnings("unchecked")
  public void selectionSort() {
    for (int i = 0; i < curr - 1; i++) {
      var min = i;
      for (int j = i + 1; j <= curr - 1; j++) {
        // 选出最小的j, 和i交换
        if (((E) data[j]).compareTo((E) data[min]) < 0) {
          min = j;
        }
      }
      if (min != i) {
        swap(min, i);
      }
    }
  }

  public void quickSort() {
    innerSort(data, 0, curr - 1);
  }

  @SuppressWarnings("unchecked")
  private void innerSort(Object[] a, int begin, int end) {
    if (end <= begin) return;
    // 将a分成两部分, 左边的小, 右边的大
    // 需要一个标杆, 就选择begin了
    var i = begin + 1;
    var j = end;
    while (i <= j) {
      while ((i <= j) && ((E) a[i]).compareTo(((E) a[begin])) <= 0) i++;

      if (i > j) break;

      while ((j >= i) && (((E) a[j]).compareTo(((E) a[begin]))) > 0) j--;

      if (i < j) {
        // 交换 i 和 j
        swap(i, j);
        i++;
        j--;
      }
    }
    if (j != begin) {
      swap(j, begin);
    }
    // 此时一定j<i了
    innerSort(a, begin, j - 1);
    innerSort(a, j + 1, end);
  }

  @SuppressWarnings("unchecked")
  public void insertionSort() {
    // i 从1开始到curr-1, 每次将i位置的元素放到左边合适的位置
    for (int i = 1; i < curr; i++) {
      int j = i;
      while (j > 0 && ((E) data[j]).compareTo((E) data[j - 1]) < 0) {
        swap(j, j - 1);
        j--;
      }
    }
  }
}
